package com.gxc.string;

/**
 * 字符串回文
 * 字符串str中，最长回文子串的长度如何求解?
    如何做到时间复杂度0(N)完成
 */
public class Manacher {

    public static void main(String[] args) {
        String str = "1221";
        //#1#2#2#1#  用插入一个相同的字符串解决，然后暴力求回文
    }

    private static int maxLcpsLength(String s) {
        if (s == null || s.length()==0) return 0;

        char[] c = manacherString(s);
        //字符串每个位置字符的回文半径
        int[] pArr = new int[s.length()];
        int R = -1;//回文最大右边界的位置    数组最右的有效区是R-1位置
        int C = -1;//重点
        int max = java.lang.Integer.MIN_VALUE;

        for (int i = 0; i < c.length; i++) {
            //如果i大于回文最大右边界，回文半径最少是1
            //i必定在C的右边
            //1.i 在 R 内，i 经过 C 对称后的 y 点的回文都在 R 对称的最左边界内，则 i 的回文半径就是 y 的回文半径
            //1.i 在 R 内，i 经过 C 对称后的 y 点的回文超出 R 对称的最左边界内，则 i 的回文半径就是 R-i
            //1.i 在 R 内，i 经过 C 对称后的 y 点的回文刚好是 R 对称的最左边界，则暴力扩R+1的字符
            pArr[i] = R>i ? Math.min(R-i, pArr[C - (i - C)]) : 1;
            //往两边暴力扩，看是否是回文

            while (i + pArr[i] < c.length && i - pArr[i] > -1) {
                //如果两边字符相等，则回文半径+1
                if (c[i + pArr[i]] == c[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    //如果两边字符不相等，跳出循环
                    break;
                }
            }
            if (i + pArr[i] > R) {
                C = i;
                //因为最后的字符 是 length -1 +1 =length,所以 数组最右的有效区是R-1位置
                R = i + pArr[i];
            }
            max = Math.max(max, pArr[i]);
        }
        //因为插入一个相同的字符串解决字符串是偶数个问题，所以添加后的字符的最大回文半径-1，就是原最大回文长度
        return max-1;
    }

    /**
     * 插入一个相同的字符串解决字符串是偶数个问题
     * @param s
     * @return
     */
    private static char[] manacherString(String s) {
        char[] chars = s.toCharArray();
        char[] c = new char[s.length()*2+1];
        int index = 0;
        for (int i = 0; i < c.length; i++) {
            c[i]=(i&1)==0 ? '#' : chars[index++];
        }
        return c;
    }
}
